package org.agile4j.algorithm.linkedlist;

/**
 * 链表工具类
 */
public class LinkedList {

    // 根节点
    private Node head = null;

    /**
     * 打印链表
     */
    public void printAll() {
        Node p = head;
        while (p != null) {
//            System.out.println(p);
            System.out.println(p.data);
            p = p.next;
        }
    }

    /**
     * 表头部插入
     *
     * @param value
     */
    public void insertToHead(int value) {
        Node newNode = new Node(value, null);
        insertToHead(newNode);
    }

    public void insertToHead(Node newNode) {
        if (head == null) {
            head = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
    }

    /**
     * 顺序插入数据
     *
     * @param value
     */
    public void insertTail(int value) {
        Node newNode = new Node(value, null);

        //空链表,可以插入新节点
        if (head == null) {
            head = newNode;
        } else {
            Node q = head;
            while (q.next != null) {
                q = q.next;
            }
//            newNode.next = q.next;
            q.next = newNode;
        }
    }

    public void insertAfter(Node p, int value) {
        if (p == null) {
            return;
        }
        Node newNode = new Node(value, null);
        insertAfter(p, newNode);
    }

    public void insertAfter(Node p, Node newNode) {
        newNode.next = p.next;
        p.next = newNode;
    }

    public void insertBefore(Node p, int value) {
        if (p == null) {
            return;
        }
        Node newNode = new Node(value, null);
        insertBefore(p, newNode);
    }

    public void insertBefore(Node p, Node newNode) {
        if (head == null) {
            return;
        }

        if (p == head) {
            insertToHead(newNode);
        } else {
            Node q = head;
            while (q.next != p) { // 获取p结点的上一个结点
                q = q.next;
            }

            if (q == null) {
                return;
            }

            newNode.next = p;
            q.next = newNode;
        }

    }

    public Node findByValue(int value) {
        if (head == null) {
            return null;
        }

        if (head.data == value) {
            return head;
        }

        Node q = head;
        while (q.data != value) {
            q = q.next;
        }
        return q;
    }

    public Node findByIndex(int index) {
        if (head == null) {
            return null;
        }
        int pos = 0;

        Node q = head;
        while (pos != index) {
            q = q.next;
            pos++;
        }
        return q;
    }

    public void deleteByNode(Node p) {
        if (head == null || p == null) {
            return;
        }

        if (head == p) {
            head = head.next;
            return;
        }

        Node q = head;
        while (q != null && q.next != p) {
            q = q.next;
        }

        if (q == null) {
            return;
        }

        q.next = p.next;
//        q.next = q.next.next;
    }

    public void deleteByIndex(int index) {
        Node p = findByIndex(index);
        deleteByNode(p);
    }

    public void deleteByValue(int value) {

    }

    public static Node createNode(int value) {
        return new Node(value, null);
    }

    public static class Node {
        private int data;
        private Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public int getData() {
            return this.data;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", next=" + next +
                    '}';
        }
    }

    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.insertToHead(1);
        linkedList.insertToHead(2);
        linkedList.insertToHead(3);
        linkedList.insertToHead(4);
//        linkedList.printAll();

        linkedList = new LinkedList();
        linkedList.insertTail(1);
        linkedList.insertTail(2);
        linkedList.insertTail(3);
        linkedList.insertTail(4);
        linkedList.insertTail(5);
        linkedList.deleteByIndex(3);
//        linkedList.deleteByNode(linkedList.findByValue(3));
        linkedList.printAll();

//        System.out.println(linkedList.findByValue(3));
//        System.out.println(linkedList.findByIndex(2));
    }
}
